//
// Created by Administrator on 2021/5/22.
//
/*有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。
 * 在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，
 * 变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。

你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。

给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-number-of-eaten-apples
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <vector>
#include <queue>
#include <iostream>
#include <map>

using namespace std;

class Solution {
public:
    int eatenApples(vector<int> &apples, vector<int> &days) {
        priority_queue<int, vector<int>, greater<>> rotDay; // 小堆顶
        int eatenApplesNum = 0;
        int i = 0;
        for (; i < days.size(); ++i) { // 遍历天数
            for (int j = 0; j < apples[i]; ++j) { // 第i天产生j个苹果
                rotDay.push(i + days[i]); // 这些苹果在i+days[i]天后腐烂
            }
            while (!rotDay.empty() and rotDay.top() <= i) rotDay.pop(); // 去除腐烂的苹果
            if (!rotDay.empty()) {
                rotDay.pop();
                ++eatenApplesNum;
            }
        }
        // 第i天后还可以吃苹果
        while (!rotDay.empty()) {
            while (!rotDay.empty() and rotDay.top() <= i) rotDay.pop(); // 去除腐烂的苹果
            if (!rotDay.empty()) {
                ++eatenApplesNum;
                rotDay.pop();
            }
            ++i;
        }
        return eatenApplesNum;
        // 超时
    }

    int eatenApples2(vector<int> &apples, vector<int> &days) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> rotDay; // 小堆顶  苹果的过期时间和数量
        int eatenApplesNum = 0;
        int i = 0;
        for (; i < days.size() or !rotDay.empty(); ++i) { // 遍历天数  i天后也能吃
            if (i < days.size()) {
                rotDay.emplace(i + days[i], apples[i]);// 第i天产生j个苹果,这些苹果在i+days[i]天后腐烂
            }
            while (!rotDay.empty() and rotDay.top().first <= i) rotDay.pop(); // 去除腐烂的苹果
            if (!rotDay.empty()) {
                auto temp = rotDay.top();
                rotDay.pop();
                if (--temp.second > 0) rotDay.push(temp);
                ++eatenApplesNum;
            }
        }
        return eatenApplesNum;
    }

    int eatenApples3(vector<int> &apples, vector<int> &days) {
        // 腐烂日期到数量
        map<int, int> day2cnt;
        // 记录数量
        int res = 0;
        int n = (int) apples.size();
        for (int i = 0; i < n || !day2cnt.empty(); ++i) {
            // 先删除已经过期的苹果
            day2cnt.erase(i);
            // 更新过期日期的苹果数量
            if (i < n && apples[i] > 0) {
                day2cnt[i + days[i]] += apples[i];
            }
            // 至少有苹果的情况
            if (!day2cnt.empty()) {
                // 先吃最早要腐烂的苹果，就是过期时间最早的
                auto iter = day2cnt.begin();
                --iter->second;
                // 计数器更新
                ++res;
                // 如果没有了，则从map表里删除掉
                if (iter->second == 0) {
                    day2cnt.erase(iter);
                }
            }
        }

        return res;
    }

};

int main() {
    vector<int> apples1{1, 2, 3, 5, 2};
    vector<int> apples2{3, 0, 0, 0, 0, 2};
    vector<int> apples3{2, 1, 10};
    vector<int> apples4{1};
    vector<int> days1{3, 2, 1, 4, 2};
    vector<int> days2{3, 0, 0, 0, 0, 2};
    vector<int> days3{2, 10, 1};
    vector<int> days4{2};
    Solution sol;
    cout << sol.eatenApples2(apples1, days1) << endl;
    cout << sol.eatenApples2(apples2, days2) << endl;
    cout << sol.eatenApples2(apples3, days3) << endl;
    cout << sol.eatenApples2(apples4, days4) << endl;
    return 0;
}